Algorithme PageRank

Énoncé

Le PageRank (PR) est un algorithme d'analyse des liens utilisé par le moteur de recherche Google pour classer des pages web. Il permet de mesurer avec un indicateur numérique la popularité d'une page web.
Le PageRank est donc l'un des indicateurs qui permettent de classer les pages du Web dans les résultats de recherche de Google (il mesure la popularité mais pas nécessairement la pertinence de la page web).
Ce système a été inventé par Larry Page, cofondateur de Google.

L'objectif de cet exercice est de comprendre le fonctionnement du PR à petite échelle.

Imaginons le réseau de 5 pages ci-dessous. Les flèches représentent les liens qui pointent vers une autre page (par exemple, la flèche de 1 vers 5 signifie qu'il existe sur la page 1 un lien vers la page 5).

Admettons qu'un internaute qui vient de consulter une page donnée à une probabilité  `p\in]0;1[` de rester sur cette page ou de choisir une autre page non liée (avec équiprobabilité entre toutes les pages) et une probabilité  \(1-p\)  de cliquer sur l'un des liens de cette page (avec équiprobabilité entre tous les liens).
Ainsi, par exemple, à partir de la page 1, il peut   rester sur la page 1 ou aller vers la page 4 (probabilité de  \(\dfrac{p}{2}\)  pour chaque) ou cliquer sur trois liens, vers les pages 2, 3 et 5 (probabilités de  \(\dfrac{1-p}{3}\)  pour chaque).

En imaginant que l'internaute surfe sur Internet sans mémoire des états précédents, ce processus est une chaîne de Markov.

1. Écrire sa matrice de transition dans le cas de l'exemple avec `p=0,7` .

2. Justifier que cette chaîne de Markov admet une unique distribution invariante et la déterminer dans le cas de l'exemple.

3. Comment peut-on utiliser cette modélisation pour classer les pages par popularité décroissante ?